package 剑指offer;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

public class _49丑数 {
    public int nthUglyNumber(int n) {
        Set<Long> set = new HashSet<Long>();
        PriorityQueue<Long> priorityQueue = new PriorityQueue<Long>();
        int[] nums = {2,3,5};
        set.add(1L);
        priorityQueue.add(1L);
        int res = 0;
        for(int i = 1; i <= n; i++){
            long poll = priorityQueue.poll();
            res = (int)poll;
            for(int num : nums){
                long next = (long)(num * poll);
                if(!set.contains(next)){
                    set.add(next);
                    priorityQueue.add(next);
                }
            }
        }
        return res;
    }
}
